/* 
 * File:   RBHash.cpp
 * Author: notnarb
 * 
 * Created on March 4, 2012, 6:10 PM
 */

#include "RBHash.h"

RBHash::RBHash() {
  insertCounter = 1;
}

RBHash::RBHash(const RBHash& orig) {
}

RBHash::~RBHash() {
}


hnode* RBHash::hashInsert(int input, rbnode* attach){

  hnode* newh = new hnode;
  newh->value = input;
  //define spot as the spot in the table where the value should be inserted
  int spot = input % HASH_SIZE;
  //insert it
  if (this->hashTable[spot] == NULL) //if there is no node already there
    this->hashTable[spot] = newh;
  else {			//otherwise
    newh->next = this->hashTable[spot];
    this->hashTable[spot] = newh;  
  }
  newh->rbP = attach;
}


//helper function for bulkLoad()
void RBHash::recurInsert(rbnode* where, int height, rbnode* parent){
  
  if (insertCounter > 100) //checks to see if insert counter is > 100 (if so, the function shouldnt run)
    return;
  if(height < ((this->insertCounter < 75) ? 7 : 6)) //if the height is supposed to increase
    {
      //insert left (create a left node)
      where->lP = new rbnode; 
      recurInsert(where->lP,height+1, where); //recursively go down a left node

      //insert on this node
      where->value = insertCounter;
      where->isBlack = 1;
      where->hP = hashInsert(insertCounter, where);
      insertCounter++;
      where->parent = parent;
      where->height = height;

      //insert right
      where->rP = new rbnode;
      recurInsert(where->rP,height+1, where);
    }
  else
    {
      if (insertCounter == 75)
	{
	  parent->rP = NULL;
	  return;
	}
      where->value = insertCounter;
      where->isBlack = (height != 7);
      where->height = height;
      where->parent = parent;
      where->hP = hashInsert(insertCounter, where);
      insertCounter++;
    }

}

    /** complete

       Name: bulkLoad()
       Parameters: none
       Returns: none
       Uses: recurInsert, hashInsert

       Description: Load the keys 1,2,...,100 into the red-black tree
       as bulk. Your program should first create a complete binary search tree
       with the keys and then color it such that all the leaves of the tree will
       be red and all the other nodes will be black.
    */    

void RBHash::bulkLoad() {
  this->rbRoot = new rbnode;
  recurInsert(this->rbRoot,1,NULL);
  this->dummy = new rbnode;
  dummy->rP = rbRoot;
  //@@@ do I need to set the parent of rbRoot?
    


}


// recursive function to insert things into the rbtree
// where - node to insert it into
// value - node to insert
void rbInsert(rbnode * &where, rbnode* value){


}

// helper function for insert -- replaces a node's parent pointer to said node with
// a different node (replacer)
void replaceChild(rbnode* replacee, rbnode* replacer){
  if (replacee->parent->lP == NULL)
    replacee->parent->rP = replacer;
  else if (replacee->parent->rP == NULL)
    replacee->parent->lP = replacer;
  else if (replacee->parent->lP->value == replacee->value)
    replacee->parent->lP = replacer;
  else if (replacee->parent->rP->value == replacee->value)
    replacee->parent->rP = replacer;
  //  replacer->parent = replacee->parent;
    


}


    /**
       Name: insert()
       Paramenters: input - integer of a value to insert into the RBH structure
       Returns: none (outputs text)
       Uses: rbInsert
       
       Description: Insert element in both the red black tree and
       the hash table, and link them correctly. Your program should return
       either "item successfully inserted" or "item already present".
    */

void RBHash::insert(int input){

  //insert it into the hash table//

  hnode* newh = new hnode;
  newh->value = input;
  //define spot as the spot in the table where the value should be inserted
  int spot = input % HASH_SIZE;
  //insert it
  if (this->hashTable[spot] == NULL) //if there is no node already there
    this->hashTable[spot] = newh;
  else {			//otherwise
    newh->next = this->hashTable[spot];
    this->hashTable[spot] = newh;
  }

  //insert it into the rbtree//
  
  rbnode* newr = new rbnode;
  newr->value = input;		//set the value
  newr->isBlack = 0;		//set it to red

  //link the two nodes
  newr->hP = newh;
  newh->rbP = newr;


  //////////Start the real insert//////////

  rbnode* temparent;
  rbnode* temgparent;

  rbnode* curpointer = this->rbRoot;

  // bool to simplify whether or not the next traversal is going to be right or left
  // if true, you're traveling down and to the right
  bool nextRight = curpointer->value < input;
  if(g_debug) std::cout << "//Starting Red Black insert!  Inserting " << input <<"\n";
  //while the pointer's corresponding child exists
  while( (nextRight ? curpointer->rP : curpointer->lP) != NULL)
    {
      if(g_debug) std::cout <<"//Currently traversing: " << curpointer->value << " and heading " << (nextRight ? "Right" : "Left") << " afterwards.\n";
      //set parent and grandparent
      if (curpointer->parent != NULL)
	temparent = curpointer->parent;
      else
	temparent = this->dummy;
      
      if (temparent->parent != NULL)
	temgparent = temparent->parent;
      else
	temparent = this->dummy;
      //first, check to see if the two children are red
      if (curpointer->rP != NULL && curpointer->lP != NULL) {
       	if (!(curpointer->rP->isBlack + curpointer->lP->isBlack)) //if both arent black
	  {
	    if (g_debug) std::cout << "both children red, lets do this\n";
	    curpointer->isBlack = false;
	    curpointer->lP->isBlack = true;
	    curpointer->rP->isBlack = true;
	    
	  }
      }
      //Hope we dont have to do a rotation now
      if (!temparent->isBlack && !curpointer->isBlack) //check both current and parent are red
	{
	  //fuck.
	  if (((curpointer->value < temparent->value) - (temparent->value < temgparent->value)) == 0) //if parent and grandparent are in the same direction (zig)
	    {
	      //single rotation
	      if (g_debug) std::cout << "CASE 2\n";
	      rbnode* b = (temparent->value < curpointer->value ? temparent->rP : temparent->lP); // b is the current pointers sister
	      replaceChild(temgparent, temparent);
	      replaceChild(temparent, b);
	      if (b != NULL) {
		replaceChild(b, temgparent);
		b->parent = temgparent;
	      }
	      temparent->parent = temgparent->parent;
	      temgparent->parent = temparent;
	      
	      curpointer->isBlack = false;
	      temparent->isBlack = true;
	      temgparent->isBlack = false;
	      
	    }
	  else //if they go in different directions (zig zag) 
	    {
	      if (g_debug) std::cout << "CASE 3\n";
	    }
	} //end checking to see if the parent is red
     
      curpointer = (nextRight ? curpointer->rP : curpointer->lP);
      nextRight = curpointer->value < input;
    }
  //before inserting, check to see if the value being inserted is black
  if (!curpointer->isBlack)
    {
      if (g_debug) std::cout << "small rotate\n";
      //set the gradparents pointer to the parent to be the current pointer instead
      replaceChild(temparent,curpointer);
      
      temparent->lP = NULL;
      temparent->rP = NULL;
      //replaceChild(curpointer,NULL);

      curpointer->parent = temgparent;
      temparent->parent = curpointer;
      (nextRight ? curpointer->lP : curpointer->rP) = temparent;
      //      (temparent->value > curpointer->value ? temparent->lP : temparent->rP) = NULL;
      //      curpointer->parent = temparent->parent;
      //      temparent->parent = curpointer;

      curpointer->isBlack = true;
      temparent->isBlack = false;
      
      
    }    
  (nextRight ? curpointer->rP : curpointer->lP) = newr;
  newr->parent = curpointer;



}


    /**
       Name: remove()
       Parameters: input - integer of the value which you wish to remove
       Use the hash table to determine where the element is, delete it from the 
       ash table and use the pointer to delete it from the red black tree. Your 
       program should return either “item successfully deleted" or “item not found"
     */

void RBHash::remove(int input){

  //@@@ STUB

}

    /**
       Name: lookup()
       Parameters: input - integer of the value you want to look up
       Returns: the depth of the item found (if found)

       Use the hash table to determine if the element is in the data structure. 
       Should return either “item found" or “item not found". If the item is found,
       return its depth in the tree
     */
void RBHash::lookup(int input){

  if (this->find(input) == NULL){
    std::cout << "Item not found\n";
    return;
  }
  std::cout << "Item found, depth = ";
  rbnode* helpnode = this->find(input)->rbP;
  int counter = 1;
  while (helpnode->parent != NULL)
    {
      helpnode = helpnode->parent;
      counter++;
    }
  std::cout << counter << std::endl;
  //@@@ TEST THIS LATER

}


// helper function for rangeup (which is a helperfunction for range) which recursively traverses down the tree
// and returns all values within the range
void rangedown(rbnode* where, int target){
  if (where->value < target) {
    if (where->lP != NULL)
      rangedown(where->lP,target);
    std::cout << " " << where->value; //ha, ha! in-order traversal
    if (where->rP != NULL)
      rangedown(where->rP,target);
  }
  if (where->value > target)
    if (where->lP != NULL)
      rangedown(where->lP, target);

  if (where->value == target) {
    if(where->lP != NULL)
      rangedown(where->lP, target);
    std::cout << " " << where->value;
    }
  

}

// helper function for range() which recursively traverses up the tree returns those within the range
// also calls rangedown on the right child of those within the range
void rangeup(rbnode* where, int target, int leftbound){
  //keep going up until you hit a node greater

  //if you go up to a node that is less than the leftbound, just keep going up
  if (where->value < leftbound) {
    rangeup(where->parent, target, leftbound);
    return;
  }

  //if you hit the node you're looking for  
  if(where->value == target){
    //print the node
    std::cout << " " << where->value ;
    //any node to the right is going to be greater than the rightbound, so dont do anything further
  }
  
  //if the node has a value less than what you are looking for
  else if(where->value < target){
    // print the value
    std::cout << " " << where->value ;
    //could potentially have the target amongst the right children
    //leave that case for range down to figure out
    rangedown(where->rP,target);
    if(where->parent != NULL) 
      rangeup(where->parent,target,leftbound);

  }
  else if(where->value > target) //useless function -- if the value is greater than the target
				 //we have already traversed the left child, any right child
				 //will also be greater, just end 
    return;

}

    /** complete
       
       Name: range()
       Parameters: left - left bound integer of the range you wish to return
                   right - right bound integer of the range you wish to return
       Returns: none
       Uses: rangeup (rangedown)

       Description: Prints out a range of all the integers between two values in a
       range using the red-black tree
     */

void RBHash::range(int left, int right){

  if (left >= right)
    {
      std::cout << "Error, left bound greater than right bound!\n";
      return;
    }
  rbnode* lnode = this->find(left)->rbP;
  rbnode* rnode = this->find(right)->rbP;
  rbnode* helpnode;

  std::cout << left; //print the first node
  helpnode = lnode->parent;

  rangeup(helpnode,rnode->value,lnode->value);
  std::cout << std::endl;

  // while (helpnode->value < left) //while the parent is less than desired (assumes there will be one greater)
  //   helpnode = helpnode->parent; //go up a level


  


  //@@@ TEST CASE: DELETE

}

     /** complete
   
	Name:successor()
	Parameters: key - integer of the value you wish to find the succesor for
	Returns: none
	Description: Uses the red black tree to print out the value next highest
	in the tree

     */

void RBHash::successor(int key){
  if(g_debug) std::cout << "//FINDING SUCCESSOR TO " << key << std::endl;
  rbnode* root = this->find(key)->rbP;
  rbnode* helpnode; //temporary pointer to traverse up and down the tree
  
  if (root->rP != NULL) //if the value has a right node, easy peasy, just keep heading down
    {
      if(g_debug) std::cout << "//Right child pointer to root found(" << root->rP->value <<")!\n";
				//keep going down the right node's left path until you hit a stop, then print that
      helpnode = root->rP; 
      while (helpnode->lP != NULL) {
	if(g_debug) std::cout << "//But it has a left pointer(" << helpnode->lP->value <<"), gonna check it out!\n";
	helpnode = helpnode->lP;    
      }  
      std::cout << helpnode->value;

    }
  else //ugh, it doesn't have a right child, does it?
    {
      //well fuck
      if(g_debug) std::cout << "//Well fuck, looks like we're climbing this tree\n";

      //lets see if any of the parents are greater than the node
      bool found = false;	// have we found a value greater?
      helpnode = root->parent;
      while (helpnode!= NULL && !found){
	if(g_debug) std::cout << "//Now inspecting " << helpnode->value << "...";
	if (helpnode->value > root->value) //hooray, we found one greater
	  {
	    if(g_debug) std::cout << "OH THANK GOODNESS, A PARENT THAT IS GREATER!!";
	    found = true;

	  }
	else
	  {
	    helpnode = helpnode->parent; //better luck next time, lets go up again
	  }
      }
      if (helpnode!= NULL)
	std::cout << helpnode->value;
      else
	std::cout << "No successor found";
    }
  std::cout << std::endl;



}

     /** complete

	Name: predecessor()
	Parameters: key - integer of the value you wish to find the predecessor for
	Returns: name
	Description: Uses the red black tree to print out the value next lowest in
	the tree

     */

void RBHash::predecessor(int key){

  rbnode* root = this->find(key)->rbP;
  rbnode* helpnode; //temporary pointer to traverse up and down the tree

  if (root->lP != NULL)
    {
      helpnode = root->lP;
      while (helpnode->rP != NULL)
	helpnode = helpnode->rP;
    }
  else
    {
      helpnode = root->parent;
      bool found = false;
      while(helpnode != NULL && !found)
	{
	  if (helpnode->value < root->value)
	    found = true;
	  else
	    helpnode = helpnode->parent;
	}
    }

  if (helpnode != NULL)
    std::cout << helpnode->value << std::endl;
  else
    std::cout << "No predecessor found\n";


}

// helper function for height()
int heightHelp(rbnode* input){
  //  if(g_debug) std::cout << "Checking node " << input->value << std::endl;
  if (input->lP == NULL){ //if the left pointer is null
    if (input->rP == NULL) //and the right pointer is null (base case)
      return 1;            //return 1
    return (heightHelp(input->rP) + 1); //otherwise just return the height of the right
  } else {
    if (input->rP == NULL) //if left pointer ISNT null and right pointer is
      return (heightHelp(input->lP) + 1); //return the height of the left
    else {				  //if both arent null
      int a = heightHelp(input->rP);	  //get both heights
      int b = heightHelp(input->lP);
      return ((a > b) ? a : b) + 1;
    }
  }

}

     /**

	Name: height()
	Parameters: none
	Returns: height of tree as an integer
	Uses: heightHelp

	Description: Finds the height of the red black tree and returns it

     */

void RBHash::height(){
  if (g_debug) std::cout << "//calculating height!\n";
  int result = heightHelp(this->rbRoot);
  std::cout << result << std::endl;
  //@@@ TEST CASES WHERE HEIGHT IS IRREGULAR

}


     /** complete

	Name: children()
	Parameters: key - integer value of the tree you wish to find the children of
	Returns: none
	Description: Prints all of the children of a given node.  Prints "no
	children" if no children are found.

      */

void RBHash::children(int key){

  rbnode* root = this->find(key)->rbP;
  if(root->lP != NULL)
    std::cout << "Left child: " << root->lP->value;
  if(root->rP != NULL)
    std::cout << " Right child: " << root->rP->value;
  if(root->lP == NULL && root->rP == NULL)
    std::cout << "no children";
  std::cout << std::endl;

}


//recursive helper function to print things preorder
void recpreorder(rbnode* input){
  std::cout << input->value << (input->isBlack ? " black" : " red");
  if(g_debug) std::cout << " " << "h=" << input->height << " p=" << input->parent->value;
  std::cout << std::endl;
  
  if (input->lP != NULL)
    recpreorder(input->lP);
  if (input->rP != NULL)
    recpreorder(input->rP);
  
}

     /**

	Name: preorder()
	Parameters: key - integer value of the node which you wish to use as root
	Returns: none
	Uses: recpreorder

	Description: Prints the elements of a subtree in preorder fashion.  Prints
	"no elements to return" if no root is found.  Also prints the color

      */

void RBHash::preorder(int key){
  if (g_debug) std::cout << "//Starting preorder\n";
  //first, find it in the hash table
  hnode* found = this->find(key);
  if(g_debug) std::cout << "//found value to preorder search - its address is " << found << std::endl;
  if(found == NULL){
    std::cout << "No elements to return\n";
    return;
  }
  rbnode* root = found->rbP;
  recpreorder(root);
  


}

//prints the hnode and calls recurPrintHT on the next node (if it exists)
void recurPrintHT(hnode* input){

      std::cout << input->value << " ";
      if (input->next != NULL)
	recurPrintHT(input->next);

}

    /**
       Name: printHT()
       Parameters: none
       Returns: none
       Uses: recurPrintHT
       Description: Prints out the hash table
     */

void RBHash::printHT(){
  for (int i = 0; i < HASH_SIZE; i++){
    hnode* rowToPrint = this->hashTable[i];
    if(rowToPrint != NULL)
      recurPrintHT(rowToPrint);
    else
      std::cout << " *Blank* ";
    std::cout << "\n";
  }

}

// finds the value in the hash table and returns a pointer to the hnode
// note: the corresponding rbnode can be found with $result->rbP
hnode* RBHash::find(int value){
  if(g_debug) std::cout << "//Starting find, looking for " << value << "...";
  int spot = value % HASH_SIZE;
  hnode* search = this->hashTable[spot];
  while(search != NULL){
    if (search->value == value) {
      if(g_debug) std::cout << "Node found!  Its address is " << search << " and the address of the node it points to is " << search->rbP << std::endl;
      return search;
    }
    else
      search = search->next;
  }
  if(g_debug) std::cout << "//search unsuccessful";
  return NULL;


}
